package leetcode.code0583;



public class Solution extends Solution583 {

	@Override
	public int minDistance(String word1, String word2) {
		if (word1 == null && word2 == null)
			return 0;
		if (word1 == null && word2 != null)
			return word2.length();
		if (word2 == null && word1 != null)
			return word1.length();
		char[] c1 = word1.toCharArray();
		char[] c2 = word2.toCharArray();
		int ans[][] = new int[c1.length + 1][c2.length + 1];
		ans[0][0] = 0;
		for (int i = 1; i <= c1.length; i++) {
			ans[i][0] = i;
		}
		for (int i = 1; i <= c2.length; i++) {
			ans[0][i] = i;
		}

		for (int i = 1; i <= c1.length; i++) {
			for (int j = 1; j <= c2.length; j++) {
				if (c1[i - 1] == c2[j - 1]) {
					ans[i][j] = ans[i - 1][j - 1];
				} else {
					ans[i][j] = Math.min(ans[i - 1][j], ans[i][j - 1]) + 1;
				}
			}
		}
		return ans[c1.length][c2.length];
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();

	}

}
